package org.everyday;

import cn.hutool.core.lang.Assert;

import java.util.Deque;
import java.util.LinkedList;

public class L946 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int i = 0, j = 0;
        Deque<Integer> deque = new LinkedList<>();
        while (j < popped.length) {
            while (i < pushed.length && pushed[i] != popped[j]) {
                deque.push(pushed[i++]);
            }
            if (i == pushed.length) return false;
            j++;
            i++;
            while (!deque.isEmpty() && j < popped.length && deque.peek() == popped[j]) {
                j++;
                deque.pop();
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Assert.isFalse(new L946().validateStackSequences(new int[]{1, 2, 3, 4, 5, 6, 7}, new int[]{1, 2, 5, 3, 6, 7, 4}));
        Assert.isTrue(new L946().validateStackSequences(new int[]{1, 2, 3, 4, 5}, new int[]{4, 5, 3, 2, 1}));
        Assert.isFalse(new L946().validateStackSequences(new int[]{1, 2, 3, 4, 5}, new int[]{4, 3, 5, 1, 2}));
        Assert.isTrue(new L946().validateStackSequences(new int[]{1, 2, 3, 4, 5}, new int[]{4, 3, 5, 2, 1}));

    }
}
